Creative content—such as music, imagery, video, film, and the like—is increasingly converted into an electronic form or stored in such a form. Often, such content is originally recorded (i.e., created) in an electronic form. More particularly, this electronic form is typically digital.
“Digital goods” is a generic label for electronically stored or transmitted content, such as creative content. Examples of digital goods include images, audio clips, video, multimedia, software, and data. Digital goods may also be called a “digital signal,” “content signal,” “digital bitstream,” “media signal,” “digital object,” “object,” and the like.
Digital goods are often distributed to consumers over private and public networks—such as Intranets and the Internet. In addition, these goods are distributed to consumers via fixed computer readable media, such as a compact disc (CD-ROM), digital versatile disc (DVD), soft magnetic diskette, or hard magnetic disk (e.g., a preloaded hard drive).
Digital goods offer many advantages over conventional analog media in terms of quality and ease of transmission. With the ever-increasing popularity of the Internet, digital goods have become a mainstay ingredient of the Web experience.
Unfortunately, it is relatively easy for a person to pirate the pristine digital content of a digital good at the expense and harm of the content owners—which includes the content author, publisher, developer, distributor, etc. The content-based industries (e.g., entertainment, music, film, etc.) that produce and distribute content are plagued by lost revenues due to digital piracy.
Modern digital pirates effectively rob content owners of their lawful compensation. Unless technology provides a mechanism to protect the rights of content owners, the creative community and culture will be impoverished.
In addition, digital goods are often stored in databases. As these databases grow, the needs for categorizing goods are becoming increasingly important. The next generation of database management software will need to accommodate solutions for fast and efficient categorization of digital goods and protection of copyrights in those digital goods.
Hashing
Hashing techniques are used to protect the rights of content owners and to speed database searching/access. Hashing techniques are used in many areas such as database management, querying, cryptography, and many other fields involving large amounts of raw data.
In general, a hashing technique maps a large block of raw data into relatively small and structured set of identifiers. These identifiers are also referred to as “hash values” or simply “hash.” By introducing a specific structure and order into raw data, the hashing function drastically reduces the size of the raw data into short identifiers. It simplifies many data management issues and reduces the computational resources needed for accessing large databases.
Mathematically, a hashing technique involves an implementation of a hashing function HK(·). That function takes a signal x as input and computes a short vector h=HK(x). That vector is an apparently random value, which is indexed by a secret key K, in some large set. That vector h is a hash value.
The use of hashing techniques are many and indeed wide-ranging: compilers, checksums, searching and sorting techniques, cryptographic message authentication, one-way hashing techniques for digital signatures, time stamping, etc. These techniques usually accept binary strings as inputs and produce a hash value having a fixed length L. Typically, these techniques use random seeds (i.e., keys) of some type.
The hash values produced by such techniques are viewed as useful because they typically have following desirable characteristics:                Apparently Uniformly Distributed—For any given input, the output hash value are uniformly distributed among the possible L-bit outputs.        Approximate Pairwise Independent—For two distinct inputs, the corresponding outputs are statistically almost independent of each other.Limitations of Conventional Hashing        
Conventional hashing techniques are used for many kinds of data. These techniques have good characteristics and are well understood. Unfortunately, digital goods with visual and/or audio content present a unique set of challenges not experienced in other digital data. This is primarily due to the unique fact that the content of such goods are subject to perceptual evaluation by human observers. Typically, perceptual evaluation is visual and/or audible.
For example, assume that the content of two digital goods are, in fact, different, but only perceptually insubstantially so. A human observer may consider the content of two digital goods to be similar. However, even perceptually insubstantially differences in content properties (such as color, pitch, intensity, phase) between two digital goods result in the two goods appearing substantially different in the digital domain.
Thus, when using conventional hashing functions, a slightly shifted version of a digital good generates a very different hash value as compared to that of the original digital good, even though the digital good is essentially identical (i.e., perceptually same) to the human observer.
The human observer is rather tolerant of certain changes in digital goods. For instance, human ears are less sensitive to changes in some ranges of frequency components of an audio signal than other ranges of frequency components.
This human tolerance can be exploited for illegal or unscrupulous purposes. For example, a pirate may use advanced audio processing techniques to remove copyright notices or embedded watermarks from audio signal without perceptually altering the audio quality.
Such malicious changes to the digital good are referred to as “attacks”, and result in changes at the data domain. Unfortunately, the human observer is unable to perceive these changes, allowing the pirate to successfully distribute unauthorized copies in an unlawful manner.
Although the human observer is tolerant of such minor (i.e., imperceptible) alterations, the digital observer—in the form of a conventional hashing technique—is not tolerant. Traditional hashing techniques are of little help identifying the common content of an original digital good and a pirated copy of such good because the original and the pirated copy hash to very different hash values. This is true even though both are perceptually identical (i.e., appear to be the same to the human observer).
Furthermore, traditional hashing techniques are of little help recognizing similar content of two digital goods. This is true even when both are perceptually similar (i.e., appear to be similar to the human observer). With conventional hashing techniques, the resulting hash values of goods with perceptually similar content are apparently completely different with a high degree of probability.
Applications for Hashing Techniques
There are many and varied applications for hashing techniques. Some include anti-piracy, content categorization, content recognition, content-based key generation, and synchronization of video signals.
Hashing techniques may be used to search for digital goods on the Web suspected of having been pirated. Like anti-piracy, semantic categorizing of the content of digital goods often requires subjective comparisons to other existing digital goods. Works of a similar nature are typically grouped into the same category. The content of digital goods may be semantically classified into any number of categories.
In addition, hashing techniques are used to generate keys based upon the content of a signal. These keys are used instead of or in addition to secret keys. Also, hashing functions may be used to synchronize input signals. Examples of such signals include video or multimedia signals. A hashing technique must be fast because synchronization is performed in real time.
Background Conclusion
Quickly and efficiently determining a hash value of a digital good is highly desireable. In addition, doing so that one can determine perceptual similarity of the content of a group of digital goods would improve anti-piracy efforts and semantic content categorization. It can improve content-based key generation and synchronization in video signals.
Accordingly, what is needed is a new hashing technique. A new technique is needed to overcome the difficulties that are brought by conventional hashing techniques when they are applied to multimedia data. Under perceptually unnoticable changes, such techniques produce different hash values with high probability.
More particularly, a new hashing technique is needed where the hash values of digital goods are proximally near each other, when the digital goods contain perceptually similar content. Furthermore, such a new hashing technique may provide a significant step towards determining whether a particular specimen of a digital good is a pirated copy of an original good.
Moreover, these new techniques would improve existing content-based key generation, which is often employed in the watermarking. These new techniques would introduce improved synchronization so as to achieve synchronization in watermarking streaming multimedia data, such as video and audio